package org.example;

public class Test4 {
    //leetcode 72 编辑距离 https://leetcode.cn/problems/edit-distance/description/
    public int minDistance(String word1, String word2) {
        /**
         * 这个问题可以转换为将word2字符串转换成word1所需要的操作次数，也可以转换为将两个字符串转换为即不等于word1
         * 也不等于word2，但是修改之后的word1==word2的最少操作次数
         * 这里使用的是将word1经过操作之后转换为word2所需要的最少操作数
         */
        char[] arr1 = word1.toCharArray(), arr2 = word2.toCharArray();
        int n1 = arr1.length, n2 = arr2.length;
        int[][] dp = new int[n1+1][n2+1];
        //初始化
        //当word1为空字符串的时候，那么需要操作的次数就是word2的长度
        for (int i = 1; i <= n1; i++) dp[i][0] = i;
        //当word2为空字符串的时候，那么需要操作的次数就是word1的长度
        for (int i = 1; i <= n2; i++) dp[0][i] = i;
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                //当arr[i-1]==arr2[j-1]的时候，就说明当前字符是不需要操作的，那么dp[i][j]就为dp[i-1][j-1]
                if (arr1[i-1] == arr2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    //如果arr[i-1]!=arr2[j-1]，那么就需要考虑是增加、删除还是替换所需要的操作次数最少了
                    //dp[i][j-1]表示word1字符串增加一个arr2[j-1]的字符之后的最少操作数，dp[i-1][j]表示删除word1[i-1]之后的最少操作数,
                    // dp[i-1][j-1]表示替换
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[n1][n2];
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        String s1 = "horse";
        String s2 = "ros";
        test4.minDistance(s1,s2);
        System.out.println(555);
    }
}
